﻿#pragma once
#include<vector>
enum State
{
	EMPTY,
	EXITS,
	DELETE,
};
template<class T>
class HashData
{
	T _data;
	State _state;
};
template<class K,class T,class KOfT>
class HashTable
{
	typedef HashData<T> HashData;
public:
	HashTable();
	~HashTable();
	bool Insert(const T& d)
	{
		size_t sz = _tables.size();
		//负载因子=数据/表的大小
		if (_num * 10 / sz >= 7)
		{
			//增容
		}
		KOfT koft;
		//1.计算位置
		size_t index = koft(d) % _tables.size();
		while (_tables[index]._state == EXITS)
		{
			if (koft(_tables[index]._data)== koft(d))
			{
				return false;
			}
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
		//2.插入
		_tables[index]._data = d;
		_tables[index]._state == EXITS;
		_num++;
	}
	HashData* Find(const T& key)
	{
		KOfT koft;
		//1.计算位置
		size_t index = koft(key) % _tables.size();
		while (_tables[index]._state != EMPTY)
		{
			if (koft(_tables[index]._data) == koft(key))
			{
				if (_tables[index]._state == EXITS)
				{
					return &_tables[index];
				}
				else if (_tables[index]._state == DELETE)
					return nullptr;     
			}
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
		return nullptr;
	}
	bool Erase(const T& key)
	{
		HashData* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_num;
			return true;
		}
		else
		{
			return false;
		}
	}

private:
	vector<HashData> _tables;
	size_t _num=0;
};

